const arr = [0, 13, 81, 43, 31, 27, 56, 92]

// 交换两个位置
const swap = (arr, i, j) => {
  const temp = arr[i]
  arr[i] = arr[j]
  arr[j] = temp
}

const median = (arr, left, right) => {
  const medianIndex = Math.floor(arr.length / 2)
  if (arr[left] > arr[right]) {
    swap(arr, left, right)
  }

  if (arr[left] > arr[median]) {
    swap(arr, left, median)
  }

  if (arr[median] > arr[right]) {
    swap(arr, median, right)
  }


  return medianIndex
}

const quickSort = (arr) => {
  if (arr.length === 0) {
    return []
  }

  const mid = median(arr, 0, arr.length - 1)
  const c = arr.splice(mid, 1)

  const l = []
  const r = []

  for (let i = 0; i < arr.length; i++) {
    if (arr[i] > c[0]) {
      r.push(arr[i])
    } else {
      l.push(arr[i])
    }
  }

  return quickSort(l).concat(c, quickSort(r))
}

console.log(quickSort(arr));
